package com.leetcode.根据数据结构分类.图;

/**
 * @author: xiaomi
 * @date: 2021/1/23
 * @description: 1319. 连通网络的操作次数
 * https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/
 */
public class B_1319_连通网络的操作次数 {

    public static void main(String[] args) {
        int n = 4;
        int[][] connections = {{0, 1}, {0, 2}, {1, 2}};
        B_1319_连通网络的操作次数 action = new B_1319_连通网络的操作次数();
        int res = action.makeConnected(4, connections);
        System.out.println("res = " + res);
    }

    /**
     * 这个就是一个最小生成树的边数量和多余边之差的问题。
     *
     * @param n           顶点个数
     * @param connections
     * @return
     */
    public int makeConnected(int n, int[][] connections) {
        //边的数量
        int m = connections.length;
        //目标边的数量
        int targetEdgeSize = n - 1;
        if (m < targetEdgeSize) {
            //第一种不可能
            return -1;
        }
        if (n < 2) {
            return 0;
        }
        int count = 2;
        InnerUnionFind unionFind = new InnerUnionFind(n);
        unionFind.union(connections[0][0], connections[0][1]);
        //记录重复的边的数量
        int loopEdgeCount = 0;
        for (int i = 1; i < m; i++) {
            if (unionFind.isSame(connections[i][0], connections[i][1])) {
                loopEdgeCount++;
            } else {
                unionFind.union(connections[i][0], connections[i][1]);
            }
        }
        return targetEdgeSize - (m - loopEdgeCount);
    }

    class InnerUnionFind {
        int[] parents;
        int[] ranks;

        public InnerUnionFind(int capacity) {
            this.parents = new int[capacity];
            this.ranks = new int[capacity];
            for (int i = 0; i < capacity; i++) {
                this.parents[i] = i;
                this.ranks[i] = 1;
            }
        }


        public int find(int index) {
            if (index != parents[index]) {
                parents[index] = find(parents[index]);
            }
            return parents[index];
        }

        public void union(int index1, int index2) {
            int p1 = find(index1);
            int p2 = find(index2);
            if (p1 == p2) {
                return;
            }
            if (ranks[p2] == ranks[p1]) {
                parents[p1] = parents[p2];
                ranks[p2]++;
            } else if (ranks[p1] < ranks[p2]) {
                parents[p1] = parents[p2];
            } else {
                parents[p2] = parents[p1];
            }
        }


        public boolean isSame(int index1, int index2) {
            return find(index1) == find(index2);
        }
    }

}
